{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #电动车游城市"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: electricCarPlan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #电动车游城市"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小明的电动车电量充满时可行驶距离为 `cnt`，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1。他将地图信息以 `[城市 A 编号,城市 B 编号,两城市间距离]` 格式整理在在二维数组 `paths`，表示城市 A、B 间存在双向通路。初始状态，电动车电量为 0。每个城市都设有充电桩，`charge[i]` 表示第 i 个城市每充 1 单位电量需要花费的单位时间。请返回小明最少需要花费多少单位时间从起点城市 `start` 抵达终点城市 `end`。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`paths = [[1,3,3],[3,2,1],[2,1,3],[0,1,4],[3,0,5]], cnt = 6, start = 1, end = 0, charge = [2,10,4,1]`\n",
    ">\n",
    ">输出：`43`\n",
    ">\n",
    ">解释：最佳路线为：1->3->0。\n",
    ">在城市 1 仅充 3 单位电至城市 3，然后在城市 3 充 5 单位电，行驶至城市 5。\n",
    ">充电用时共 3\\*10 + 5\\*1= 35\n",
    ">行驶用时 3 + 5 = 8，此时总用时最短 43。\n",
    "![image.png](https://pic.leetcode-cn.com/1616125304-mzVxIV-image.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`paths = [[0,4,2],[4,3,5],[3,0,5],[0,1,5],[3,2,4],[1,2,8]], cnt = 8, start = 0, end = 2, charge = [4,1,1,3,2]`\n",
    ">\n",
    ">输出：`38`\n",
    ">\n",
    ">解释：最佳路线为：0->4->3->2。\n",
    ">城市 0 充电 2 单位，行驶至城市 4 充电 8 单位，行驶至城市 3 充电 1 单位，最终行驶至城市 2。\n",
    ">充电用时 4\\*2+2\\*8+3\\*1 = 27\n",
    ">行驶用时 2+5+4 = 11，总用时最短 38。\n",
    "\n",
    "**提示：**\n",
    "- `1 <= paths.length <= 200`\n",
    "- `paths[i].length == 3`\n",
    "- `2 <= charge.length == n <= 100`\n",
    "- `0 <= path[i][0],path[i][1],start,end < n`\n",
    "- `1 <= cnt <= 100`\n",
    "- `1 <= path[i][2] <= cnt`\n",
    "- `1 <= charge[i] <= 100`\n",
    "- 题目保证所有城市相互可以到达"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [DFPeFJ](https://leetcode.cn/problems/DFPeFJ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [DFPeFJ](https://leetcode.cn/problems/DFPeFJ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,3],[3,2,1],[2,1,3],[0,1,4],[3,0,5]]\\n6\\n1\\n0\\n[2,10,4,1]', '[[0,4,2],[4,3,5],[3,0,5],[0,1,5],[3,2,4],[1,2,8]]\\n8\\n0\\n2\\n[4,1,1,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nodes_begin = [[inf]*(cnt+1) for i in range(len(charge))]\n",
    "        pq = [(0,start,0)]   \n",
    "        g = [[] for _ in range(len(charge))]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        while pq:\n",
    "            dis, v,power = heapq.heappop(pq)\n",
    "            if v == end:\n",
    "                return dis\n",
    "            nodes_begin[v][power] = dis\n",
    "            if power < cnt and charge[v]+dis < nodes_begin[v][power+1]:\n",
    "                heapq.heappush(pq,[dis+charge[v],v,power+1])\n",
    "            for y,z in g[v]:\n",
    "                if power>=z and nodes_begin[y][power-z] > dis + z:\n",
    "                    nodes_begin[y][power-z] = dis + z\n",
    "                    heapq.heappush(pq,[dis + z,y,power-z])\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        dist = [[inf]*(cnt+1) for _ in range(n)]\n",
    "        dist[start][0] = 0\n",
    "        q = [(0,start,0)]\n",
    "        g = [[]*(n) for _ in range(n) ]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        \n",
    "        while q:\n",
    "            d,v,t = heappop(q)\n",
    "            if d > dist[v][t]:\n",
    "                continue\n",
    "            if t < cnt and charge[v]+d < dist[v][t+1]:\n",
    "                heappush(q,(charge[v]+d,v,t+1))\n",
    "                dist[v][t+1] = charge[v]+d\n",
    "            if v == end:\n",
    "                return d\n",
    "            for y,z in g[v]:\n",
    "                if t >= z and d+z < dist[y][t-z]:\n",
    "                    dist[y][t-z] = d+z\n",
    "                    heappush(q,(d+z,y,t-z))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nodes_begin = [[inf]*(cnt+1) for i in range(len(charge))]\n",
    "        pq = [(0,start,0)]   \n",
    "        g = [[] for _ in range(len(charge))]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        while pq:\n",
    "            dis, v,power = heapq.heappop(pq)\n",
    "            if dis > nodes_begin[v][power]:\n",
    "                continue\n",
    "            if v == end:\n",
    "                return dis\n",
    "            nodes_begin[v][power] = dis\n",
    "            if power < cnt and charge[v]+dis < nodes_begin[v][power+1]:\n",
    "                heapq.heappush(pq,[dis+charge[v],v,power+1])\n",
    "            for y,z in g[v]:\n",
    "                if power>=z and nodes_begin[y][power-z] > dis + z:\n",
    "                    nodes_begin[y][power-z] = dis + z\n",
    "                    heapq.heappush(pq,[dis + z,y,power-z])\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nodes_begin = [[inf]*(cnt+1) for i in range(len(charge))]\n",
    "        pq = [(0,start,0)]   \n",
    "        g = [[] for _ in range(len(charge))]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        while pq:\n",
    "            dis, v,power = heapq.heappop(pq)\n",
    "            if dis > nodes_begin[v][power]:\n",
    "                continue\n",
    "            if v == end:\n",
    "                return dis\n",
    "            nodes_begin[v][power] = dis\n",
    "            if power < cnt:\n",
    "                heapq.heappush(pq,[nodes_begin[v][power]+charge[v],v,power+1])\n",
    "            for y,z in g[v]:\n",
    "                if power>=z and nodes_begin[y][power-z] > nodes_begin[v][power] + z:\n",
    "                    nodes_begin[y][power-z] = nodes_begin[v][power] + z\n",
    "                    heapq.heappush(pq,[nodes_begin[y][power-z],y,power-z])\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections, heapq\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        n = len(charge)\n",
    "        for edge in paths:\n",
    "            graph[edge[0]].append([edge[1], edge[2]])\n",
    "            graph[edge[1]].append([edge[0], edge[2]])\n",
    "        distance = [[1000000 for _ in range(cnt+1)] for _ in range(n)]\n",
    "        distance[start][0] = 0\n",
    "        visited = [[False for _ in range(cnt+1)] for _ in range(n)]\n",
    "        li = []\n",
    "        heapq.heappush(li, [0, start, 0])\n",
    "        while li:\n",
    "            record = heapq.heappop(li)\n",
    "            cost = record[0]\n",
    "            cur = record[1]\n",
    "            power = record[2]\n",
    "            if visited[cur][power]:\n",
    "                continue\n",
    "            if cur == end:\n",
    "                return cost\n",
    "            visited[cur][power]\n",
    "            if power < cnt:\n",
    "                if not visited[cur][power+1] and cost + charge[cur] < distance[cur][power+1]:\n",
    "                    distance[cur][power+1] = cost + charge[cur]\n",
    "                    heapq.heappush(li, [cost + charge[cur], cur, power+1])\n",
    "            for edge in graph[cur]:\n",
    "                restpower = power - edge[1]\n",
    "                nextcity = edge[0]\n",
    "                ncost = cost + edge[1]\n",
    "                if restpower >= 0 and not visited[nextcity][restpower] and ncost < distance[nextcity][restpower]:\n",
    "                    distance[nextcity][restpower] = ncost\n",
    "                    heapq.heappush(li, [ncost, nextcity, restpower])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nodes_begin = [[inf]*(cnt+1) for i in range(len(charge))]\n",
    "        pq = [(0,start,0)]   \n",
    "        g = [[] for _ in range(len(charge))]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        while pq:\n",
    "            dis, v,power = heapq.heappop(pq)\n",
    "            if v == end:\n",
    "                return dis\n",
    "            nodes_begin[v][power] = dis\n",
    "            if power < cnt and charge[v]+dis < nodes_begin[v][power+1]:\n",
    "                heapq.heappush(pq,[dis+charge[v],v,power+1])\n",
    "            for y,z in g[v]:\n",
    "                if power>=z and nodes_begin[y][power-z] > dis + z:\n",
    "                    nodes_begin[y][power-z] = dis + z\n",
    "                    heapq.heappush(pq,[dis + z,y,power-z])\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        roadMap = defaultdict(list)\n",
    "        for f,t,d in paths:\n",
    "            roadMap[f].append([t,d])\n",
    "            roadMap[t].append([f,d])\n",
    "        heap=[(0,start,0)]\n",
    "\n",
    "        nodes=[[10**10]*(cnt+1) for i in range(len(charge))]\n",
    "        nodes[start][0]=0\n",
    "        while len(heap)>0:\n",
    "            fee,f,res = heapq.heappop(heap)\n",
    "            # if fee>nodes[f][left]:\n",
    "            #     continue\n",
    "            if f==end:\n",
    "                # print(nodes)\n",
    "                # print(fee,res,f)\n",
    "                return fee\n",
    "            if res<cnt:\n",
    "                nfee = fee+charge[f]\n",
    "                if nodes[f][res+1]>nfee:\n",
    "                    nodes[f][res+1]=nfee\n",
    "                    heapq.heappush(heap,(nfee,f,res+1))\n",
    "                    \n",
    "            for t,dist in roadMap[f]:\n",
    "                if res>=dist:\n",
    "                    nfee = fee + dist \n",
    "                    # print(f,t,roadMap[f])\n",
    "                    if nodes[t][res-dist]>nfee:\n",
    "                        nodes[t][res - dist]=nfee\n",
    "                        heapq.heappush(heap,(nfee,t,res - dist ))\n",
    "\n",
    "\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        # paths is sparse, sort by dist for better performance\n",
    "        paths_dict = {}\n",
    "        for a, b, d in paths:\n",
    "            if a not in paths_dict:\n",
    "                paths_dict[a] = {}\n",
    "            paths_dict[a][b] = min(d, paths_dict[a].get(b, 101))\n",
    "            if b not in paths_dict:\n",
    "                paths_dict[b] = {}\n",
    "            paths_dict[b][a] = min(d, paths_dict[b].get(a, 101))\n",
    "\n",
    "        city_cnt_mintime = [ [9999999999999999 for _ in range(cnt+1)] for _ in charge ]\n",
    "        city_cnt_mintime[start][0] = 0\n",
    "        new_mintime = [[start, 0]]\n",
    "        while len(new_mintime) > 0:\n",
    "            city, c = new_mintime[0]\n",
    "            \n",
    "            if c < cnt:\n",
    "                if city_cnt_mintime[city][c + 1] > city_cnt_mintime[city][c] + charge[city]:\n",
    "                    city_cnt_mintime[city][c + 1] = city_cnt_mintime[city][c] + charge[city]\n",
    "                    new_mintime.append([city, c + 1])\n",
    " \n",
    "            for city2, dist in paths_dict[city].items():\n",
    "                if c < dist:\n",
    "                    continue\n",
    "                if city_cnt_mintime[city2][c - dist] > city_cnt_mintime[city][c] + dist:\n",
    "                    city_cnt_mintime[city2][c - dist] = city_cnt_mintime[city][c] + dist\n",
    "                    new_mintime.append([city2, c - dist])\n",
    "            \n",
    "            new_mintime.pop(0)\n",
    "        \n",
    "        return city_cnt_mintime[end][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths, cnt, start, end, charge):\n",
    "        INF = float('inf')\n",
    "        n = len(charge)\n",
    "        dist = [[INF for _ in range(cnt + 1)] for _ in range(n)]\n",
    "        dist[start][0] = 0\n",
    "        \n",
    "        adj = [[] for _ in range(n)]\n",
    "        for u, v, w in paths:\n",
    "            adj[u].append((v, w))\n",
    "            adj[v].append((u, w))\n",
    "\n",
    "        pq = [(0, start, 0)] # (time, node, charge)\n",
    "        \n",
    "        while pq:\n",
    "            t, u, c = heappop(pq)\n",
    "            if t > dist[u][c]:\n",
    "                continue\n",
    "            if u == end:\n",
    "                return t\n",
    "            \n",
    "            # Charge the vehicle for one minute\n",
    "            if c < cnt:\n",
    "                nt = t + charge[u]\n",
    "                if nt < dist[u][c + 1]:\n",
    "                    dist[u][c + 1] = nt\n",
    "                    heappush(pq, (nt, u, c + 1))\n",
    "            \n",
    "            # Traverse the edge if possible\n",
    "            for v, w in adj[u]:\n",
    "                if c >= w and t + w < dist[v][c - w]:\n",
    "                    dist[v][c - w] = t + w\n",
    "                    heappush(pq, (t + w, v, c - w))\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        dist = [[inf]*(cnt+1) for _ in range(n)]\n",
    "        dist[start][0] = 0\n",
    "        q = [(0,start,0)]\n",
    "        g = [[]*(n) for _ in range(n) ]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        \n",
    "        while q:\n",
    "            d,v,t = heappop(q)\n",
    "            if d > dist[v][t]:\n",
    "                continue\n",
    "            if t < cnt and charge[v]+d < dist[v][t+1]:\n",
    "                heappush(q,(charge[v]+d,v,t+1))\n",
    "                dist[v][t+1] = charge[v]+d\n",
    "            if v == end:\n",
    "                return d\n",
    "            for y,z in g[v]:\n",
    "                if t >= z and d+z < dist[y][t-z]:\n",
    "                    dist[y][t-z] = d+z\n",
    "                    heappush(q,(d+z,y,t-z))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nodes_begin = [[inf]*(cnt+1) for i in range(len(charge))]\n",
    "        pq = [(0,start,0)]   \n",
    "        g = [[] for _ in range(len(charge))]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        while pq:\n",
    "            dis, v,power = heapq.heappop(pq)\n",
    "            if dis > nodes_begin[v][power]:\n",
    "                continue\n",
    "            if v == end:\n",
    "                return dis\n",
    "            nodes_begin[v][power] = dis\n",
    "            if power < cnt:\n",
    "                heapq.heappush(pq,[dis+charge[v],v,power+1])\n",
    "            for y,z in g[v]:\n",
    "                if power>=z and nodes_begin[y][power-z] > dis + z:\n",
    "                    nodes_begin[y][power-z] = dis + z\n",
    "                    heapq.heappush(pq,[nodes_begin[y][power-z],y,power-z])\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths, cnt, start, end, charge):\n",
    "        INF=0x3f3f3f\n",
    "        n=len(charge)\n",
    "        dist=[[INF]*(cnt+1)for _ in range(n)]\n",
    "        dist[start][0]=0\n",
    "\n",
    "        adj =[[]for _ in range(n)]\n",
    "        for path in paths:\n",
    "            u,v,w=path[0],path[1],path[2]\n",
    "            adj[u].append((v,w))\n",
    "            adj[v].append((u,w))\n",
    "        pq=[(0,start,0)]\n",
    "        while pq:\n",
    "            t,u,c=heapq.heappop(pq)\n",
    "\n",
    "            if t>dist[u][c]:\n",
    "                continue\n",
    "            if u==end:\n",
    "                return t\n",
    "            if c<cnt:\n",
    "                nt=t+charge[u]\n",
    "                if nt<dist[u][c+1]:\n",
    "                    dist[u][c+1]=nt\n",
    "                    heapq.heappush(pq,(nt,u,c+1))\n",
    "            for v,w in adj[u]:\n",
    "                if c>=w and t+w <dist[v][c-w]:\n",
    "                    dist[v][c-w]=t+w\n",
    "                    heapq.heappush(pq,(t+w,v,c-w))\n",
    "        return-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths, cnt, start, end, charge):\n",
    "        INF = 0x3f3f3f3f\n",
    "        n = len(charge)\n",
    "        \n",
    "        # 初始化距离矩阵，表示从起点到达每个节点时的最小时间\n",
    "        dist = [[INF] * (cnt + 1) for _ in range(n)]\n",
    "        dist[start][0] = 0\n",
    "\n",
    "        # 构建邻接表表示图\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for path in paths:\n",
    "            u, v, w = path[0], path[1], path[2]\n",
    "            adj[u].append((v, w))\n",
    "            adj[v].append((u, w))\n",
    "\n",
    "        # 优先队列，用于选择当前最小时间的节点\n",
    "        pq = [(0, start, 0)]\n",
    "\n",
    "        while pq:\n",
    "            t, u, c = heapq.heappop(pq)\n",
    "            \n",
    "            # 如果当前时间已经大于已知的最小时间，跳过\n",
    "            if t > dist[u][c]:\n",
    "                continue\n",
    "            \n",
    "            # 如果到达终点，返回当前时间\n",
    "            if u == end:\n",
    "                return t\n",
    "\n",
    "            # 如果当前电量未达到最大值，尝试充电\n",
    "            if c < cnt:\n",
    "                nt = t + charge[u]\n",
    "                if nt < dist[u][c + 1]:\n",
    "                    dist[u][c + 1] = nt\n",
    "                    heapq.heappush(pq, (nt, u, c + 1))\n",
    "\n",
    "            # 尝试移动到每个邻居节点\n",
    "            for v, w in adj[u]:\n",
    "                # 如果有足够的电量，尝试移动到下一个城市并更新状态\n",
    "                if c >= w and t + w < dist[v][c - w]:\n",
    "                    dist[v][c - w] = t + w\n",
    "                    heapq.heappush(pq, (t + w, v, c - w))\n",
    "\n",
    "        return -1  # 如果无法到达终点，返回-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nodes_begin = [[inf]*(cnt+1) for i in range(len(charge))]\n",
    "        pq = [(0,start,0)]   \n",
    "        g = [[] for _ in range(len(charge))]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        while pq:\n",
    "            dis, v,power = heapq.heappop(pq)\n",
    "            if dis > nodes_begin[v][power]:\n",
    "                continue\n",
    "            if v == end:\n",
    "                return dis\n",
    "            nodes_begin[v][power] = dis\n",
    "            if power < cnt and charge[v]+dis < nodes_begin[v][power+1]:\n",
    "                heapq.heappush(pq,[dis+charge[v],v,power+1])\n",
    "            for y,z in g[v]:\n",
    "                if power>=z and nodes_begin[y][power-z] > dis + z:\n",
    "                    nodes_begin[y][power-z] = dis + z\n",
    "                    heapq.heappush(pq,[dis + z,y,power-z])\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n,m = len(charge),len(paths)\n",
    "        heads = [-1]*n\n",
    "        edges = [-1]*m*2\n",
    "        weight = [-1]*m*2\n",
    "        to = [-1]*m*2\n",
    "        linec = 0\n",
    "        for u,v,w in paths:\n",
    "            edges[linec] = heads[u]\n",
    "            to[linec] = v\n",
    "            heads[u] = linec\n",
    "            weight[linec] = w\n",
    "            linec += 1\n",
    "            edges[linec] = heads[v]\n",
    "            to[linec] = u\n",
    "            heads[v] = linec\n",
    "            weight[linec] = w\n",
    "            linec += 1\n",
    "        # 0-cost,1-city,2-charge\n",
    "        q = [(0,start,0)]\n",
    "        cost = [[inf]*(cnt+1) for _ in range(n)]\n",
    "        vis = [[False]*(cnt+1) for _ in range(n)]\n",
    "        while q:\n",
    "            uco,u,ucg = heapq.heappop(q)\n",
    "            vis[u][ucg] = True\n",
    "            if u == end:\n",
    "                return uco\n",
    "            # charge one\n",
    "            if ucg < cnt and not vis[u][ucg+1] and uco+charge[u] < cost[u][ucg+1]:\n",
    "                cost[u][ucg+1] = uco+charge[u]\n",
    "                heapq.heappush(q, (uco+charge[u],u,ucg+1))\n",
    "            # no charge\n",
    "            line = heads[u]\n",
    "            while line != -1:\n",
    "                v = to[line]\n",
    "                w = weight[line]\n",
    "                if ucg>=w and not vis[v][ucg-w] and uco+w < cost[v][ucg-w]:\n",
    "                    cost[v][ucg-w] = uco+w\n",
    "                    heapq.heappush(q, (cost[v][ucg-w],v,ucg-w))\n",
    "                line = edges[line]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in paths:\n",
    "            graph[a].append([b, c])\n",
    "            graph[b].append([a, c])\n",
    "        queue = collections.deque([[start, 0]])\n",
    "        dis = [[float('inf') for _ in range(n)] for _ in range(cnt + 1)]\n",
    "        dis[0][start] = 0\n",
    "        while queue:\n",
    "            cur, power = queue.popleft()\n",
    "            if power + 1 <= cnt and dis[power + 1][cur] > dis[power][cur] + charge[cur]:\n",
    "                dis[power + 1][cur] = dis[power][cur] + charge[cur]\n",
    "                queue.append([cur, power + 1])\n",
    "            for nei, cost in graph[cur]:\n",
    "                if power >= cost and dis[power - cost][nei] > dis[power][cur] + cost:\n",
    "                    dis[power - cost][nei] = dis[power][cur] + cost\n",
    "                    queue.append([nei, power - cost])\n",
    "        res = float('inf')\n",
    "        for i in range(cnt + 1):\n",
    "            res = min(res, dis[i][end])\n",
    "        return res if res != float('inf') else - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,w in paths:\n",
    "            graph[u].append((v,w))\n",
    "            graph[v].append((u,w))\n",
    "        \n",
    "        # n个节点，每个节点有0-cnt cnt+1个拆分节点\n",
    "        # 对于第i个节点的j电量节点，i*(cnt+1)+j\n",
    "        dist = [float('inf')]*(n*(cnt+1))\n",
    "        dist[start*(cnt+1)] = 0\n",
    "        queue = [(0,start,0)]\n",
    "\n",
    "        while queue:\n",
    "            dis,x,c = heapq.heappop(queue)\n",
    "            cur_pos = x*(cnt+1)+c\n",
    "            if dist[cur_pos]<dis:\n",
    "                continue\n",
    "            if c<cnt:\n",
    "                charge_dist = dis + charge[x]\n",
    "                if charge_dist < dist[cur_pos+1]:\n",
    "                    dist[cur_pos+1] = charge_dist\n",
    "                    heapq.heappush(queue, (dist[cur_pos+1], x, c+1))\n",
    "\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if c>=nextD:\n",
    "                    rc = c - nextD\n",
    "                    n_pos = nextN*(cnt+1)+rc\n",
    "                    if dis + nextD < dist[n_pos]:\n",
    "                        dist[n_pos] = dis + nextD\n",
    "                        heapq.heappush(queue, (dist[n_pos], nextN, rc))\n",
    "                pass\n",
    "            pass\n",
    "\n",
    "        return dist[end*(cnt+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths, cnt, start, end, charge):\n",
    "        INF=float('inf')\n",
    "        n =len(charge)\n",
    "        dist=[[INF]*(cnt+1) for _ in range(n)]\n",
    "        dist[start][0]  =0\n",
    "\n",
    "        adj =[[] for _ in range(n)]\n",
    "        for path in paths:\n",
    "            u,v,w=path[0],path[1],path[2]\n",
    "            adj[u].append((v, w))\n",
    "            adj[v].append((u, w))\n",
    "\n",
    "        pq= [(0,start,0)]\n",
    "\n",
    "        while pq:\n",
    "            t,u,c=heapq.heappop(pq)\n",
    "\n",
    "            if t>dist[u][c]:\n",
    "                continue\n",
    "            if u==end:\n",
    "                return t\n",
    "\n",
    "            if c<cnt:\n",
    "                nt=t+charge[u]\n",
    "                if nt<dist[u][c+1]:\n",
    "                    dist[u][c+1]=nt\n",
    "                    heapq.heappush(pq,(nt,u,c+1))\n",
    "\n",
    "            for v,w in adj[u]:\n",
    "                if c>=w and t+w <dist[v][c-w]:\n",
    "                    dist[v][c-w ]=t+w\n",
    "                    heapq.heappush(pq,(t+w,v,c-w))\n",
    "\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(paths)\n",
    "        full_battery = cnt\n",
    "\n",
    "        adjvex = defaultdict(list)      #邻接表\n",
    "        for x, y, d in paths:\n",
    "            adjvex[x].append((d, y))\n",
    "            adjvex[y].append((d, x))\n",
    "\n",
    "        memo = [[float('inf') for _ in range(full_battery + 1)] for _ in range(n)]\n",
    "        minHeap = []\n",
    "        heapq.heappush(minHeap, (0, start, 0))\n",
    "        memo[start][0] = 0\n",
    "        while minHeap:\n",
    "            cost, x, bat = heapq.heappop(minHeap)\n",
    "            if x == end:\n",
    "                return cost\n",
    "            if cost > memo[x][bat]:\n",
    "                continue\n",
    "            if bat < full_battery:\n",
    "                if cost + charge[x] < memo[x][bat + 1]:\n",
    "                    memo[x][bat + 1] = cost + charge[x]\n",
    "                    heapq.heappush(minHeap, (cost + charge[x], x, bat + 1 ))    #充一格电\n",
    "            for d, y in adjvex[x]:\n",
    "                if bat >= d and cost + d < memo[y][bat - d]:\n",
    "                    memo[y][bat - d] = cost + d\n",
    "                    heapq.heappush(minHeap, (cost + d, y, bat - d))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(paths)\n",
    "        full_battery = cnt\n",
    "\n",
    "        adjvex = defaultdict(list)      #邻接表\n",
    "        for x, y, d in paths:\n",
    "            adjvex[x].append((d, y))\n",
    "            adjvex[y].append((d, x))\n",
    "\n",
    "        memo = [[float('inf') for _ in range(full_battery + 1)] for _ in range(n)]\n",
    "        minHeap = []\n",
    "        heapq.heappush(minHeap, (0, start, 0))\n",
    "        memo[start][0] = 0\n",
    "        while minHeap:\n",
    "            cost, x, bat = heapq.heappop(minHeap)\n",
    "            if x == end:\n",
    "                return cost\n",
    "            if cost > memo[x][bat]:\n",
    "                continue\n",
    "            if bat < full_battery:\n",
    "                if cost + charge[x] < memo[x][bat + 1]:\n",
    "                    memo[x][bat + 1] = cost + charge[x]\n",
    "                    heapq.heappush(minHeap, (cost + charge[x], x, bat + 1 ))    #充一格电\n",
    "            for d, y in adjvex[x]:\n",
    "                if bat >= d and cost + d < memo[y][bat - d]:\n",
    "                    memo[y][bat - d] = cost + d\n",
    "                    heapq.heappush(minHeap, (cost + d, y, bat - d))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(paths)\n",
    "        full_battery = cnt\n",
    "\n",
    "        adjvex = defaultdict(list)      #邻接表\n",
    "        for x, y, d in paths:\n",
    "            adjvex[x].append((d, y))\n",
    "            adjvex[y].append((d, x))\n",
    "\n",
    "        memo = [[float('inf') for _ in range(full_battery + 1)] for _ in range(n)]\n",
    "        minHeap = []\n",
    "        heapq.heappush(minHeap, (0, start, 0))\n",
    "        memo[start][0] = 0\n",
    "        while minHeap:\n",
    "            cost, x, bat = heapq.heappop(minHeap)\n",
    "            if x == end:\n",
    "                return cost\n",
    "            if cost > memo[x][bat]:\n",
    "                continue\n",
    "            if bat < full_battery:\n",
    "                if cost + charge[x] < memo[x][bat + 1]:\n",
    "                    memo[x][bat + 1] = cost + charge[x]\n",
    "                    heapq.heappush(minHeap, (cost + charge[x], x, bat + 1 ))    #充一格电\n",
    "            for d, y in adjvex[x]:\n",
    "                if bat >= d and cost + d < memo[y][bat - d]:\n",
    "                    memo[y][bat - d] = cost + d\n",
    "                    heapq.heappush(minHeap, (cost + d, y, bat - d))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        dct = defaultdict(lambda: defaultdict(lambda: float('inf')))\n",
    "        for i, j, dis in paths:\n",
    "            if dis < dct[i][j]:\n",
    "                dct[i][j] = dis\n",
    "            if dis < dct[j][i]:\n",
    "                dct[j][i] = dis\n",
    "\n",
    "        stack = [[0, 0, start]]\n",
    "        visit = [-1]*n\n",
    "        while stack:\n",
    "            tm, cha, pos = heapq.heappop(stack)\n",
    "\n",
    "            if cha <= visit[pos]:\n",
    "                continue\n",
    "            visit[pos] = cha\n",
    "\n",
    "            if pos == end:\n",
    "                return tm\n",
    "\n",
    "            for nex in dct[pos]:\n",
    "                if cha >= dct[pos][nex] and cha-dct[pos][nex] > visit[nex]:\n",
    "                    heapq.heappush(stack, [tm+dct[pos][nex], cha-dct[pos][nex], nex])\n",
    "                elif 0 > visit[nex]:\n",
    "                    cost_nex = dct[pos][nex] + tm + (dct[pos][nex] - cha) * charge[pos]\n",
    "                    heapq.heappush(stack, [cost_nex, 0, nex])\n",
    "\n",
    "            if cha < cnt:\n",
    "                heapq.heappush(stack, [tm + charge[pos], cha + 1, pos])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int: # 难点在于图的构造\n",
    "        n = len(charge)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for s, e, w in paths:\n",
    "            g[s].append((e, w))\n",
    "            g[e].append((s, w))\n",
    "        # 总用时， 节点， 电量\n",
    "        q = []\n",
    "        heapq.heappush(q, (0, start, 0))\n",
    "        d = dict()\n",
    "        while q:\n",
    "            w, x, c = heapq.heappop(q)\n",
    "            if (x, c) in d:\n",
    "                continue\n",
    "            if (x, c) == (end, 0):\n",
    "                return w\n",
    "            d[(x, c)] = w\n",
    "            for v, w1 in g[x]:\n",
    "                if c >= w1 and (v, c - w1) not in d:\n",
    "                    heapq.heappush(q, (w + w1, v, c - w1))\n",
    "            if c < cnt:\n",
    "                heapq.heappush(q, (w + charge[x], x, c + 1))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        visited = set()\n",
    "        n = len(charge)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for u, v, w in paths:\n",
    "            children[u].append([v, w])\n",
    "            children[v].append([u, w])\n",
    "        pq = [(0, start, 0)] #cost, \n",
    "        while pq:\n",
    "            w, u, c = heapq.heappop(pq)\n",
    "            if (u, c) in visited: continue\n",
    "            visited.add((u, c))\n",
    "            if (u, c) == (end, 0): return w\n",
    "            for nv, nw in children[u]:\n",
    "                if nw <= c and (nv, c-nw) not in visited:\n",
    "                    heapq.heappush(pq, (w+nw, nv, c-nw))\n",
    "            if c < cnt:\n",
    "                heapq.heappush(pq, (w+charge[u], u, c+1))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.graph = {}\n",
    "\n",
    "    def add_edge(self, f, t, cost):\n",
    "        if f not in self.graph:\n",
    "            self.graph[f] = {}\n",
    "        if t not in self.graph[f]:\n",
    "            self.graph[f][t] = cost\n",
    "        else:\n",
    "            self.graph[f][t] = min(self.graph[f][t], cost)\n",
    "\n",
    "\n",
    "def su(arr, poses, dp, index):\n",
    "    parent = index//2\n",
    "    while parent > 0 and dp[arr[parent][1]][arr[parent][0]] > dp[arr[index][1]][arr[index][0]]:\n",
    "        poses[arr[parent][1]][arr[parent][0]], poses[arr[index][1]][arr[index][0]] = index, parent\n",
    "        arr[parent], arr[index] = arr[index],arr[parent]\n",
    "        index = parent\n",
    "        parent = index//2\n",
    "\n",
    "\n",
    "def add(arr, poses,dp, item):\n",
    "    l = len(arr)\n",
    "    arr.append(item)\n",
    "    poses[item[1]][item[0]] = l\n",
    "    su(arr, poses,dp, l)\n",
    "\n",
    "\n",
    "def sd(arr, poses,dp):\n",
    "    i = 1\n",
    "    while i*2 < len(arr):\n",
    "        parent = i\n",
    "        i*=2\n",
    "        if i+1 < len(arr) and dp[arr[i+1][1]][arr[i+1][0]] < dp[arr[i][1]][arr[i][0]]:\n",
    "            i += 1\n",
    "        if dp[arr[i][1]][arr[i][0]] < dp[arr[parent][1]][arr[parent][0]]:\n",
    "            poses[arr[i][1]][arr[i][0]] = parent\n",
    "            poses[arr[parent][1]][arr[parent][0]] = i\n",
    "            arr[i], arr[parent] = arr[parent], arr[i]\n",
    "        else:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        g = Graph()\n",
    "        for path in paths:\n",
    "            g.add_edge(path[0], path[1], path[2])\n",
    "            g.add_edge(path[1], path[0], path[2])\n",
    "        dp = [[sys.maxsize]*(cnt+1) for i in range(len(charge))]\n",
    "        vis = [[False]*(cnt+1) for i in range(len(charge))]\n",
    "        poses = [[1]*(cnt+1) for i in range(len(charge))]\n",
    "        dp[start][0] = 0\n",
    "        vis[start][0] = True\n",
    "        q = [(0,0),(0, start)]\n",
    "        while len(q) > 1:\n",
    "            (cge, pos) = q[1]\n",
    "            q[1] = q[-1]\n",
    "            q.pop()\n",
    "            if len(q)>1:\n",
    "                sd(q, poses,dp)\n",
    "            vis[pos][cge] = False\n",
    "            for i in range(1, cnt+1):  # 补充电量\n",
    "                if i+cge > cnt:\n",
    "                    break\n",
    "                if dp[pos][cge]+i*charge[pos] < dp[pos][i+cge]:\n",
    "                    dp[pos][i+cge] = dp[pos][cge]+i*charge[pos]\n",
    "                    if not vis[pos][i+cge]:\n",
    "                        vis[pos][i+cge] = True\n",
    "                        add(q, poses, dp,(i+cge, pos))\n",
    "                    else:\n",
    "                        su(q, poses, dp,poses[pos][i+cge])\n",
    "            if pos in g.graph:\n",
    "                for nxt in g.graph[pos]:\n",
    "                    c = g.graph[pos][nxt]\n",
    "                    if cge-c >= 0 and dp[pos][cge]+c < dp[nxt][cge-c]:\n",
    "                        dp[nxt][cge-c] = dp[pos][cge]+c\n",
    "                        if not vis[nxt][cge-c]:\n",
    "                            vis[nxt][cge-c] = True\n",
    "                            add(q, poses,dp, (cge-c, nxt))\n",
    "                        else:\n",
    "                            su(q, poses,dp, poses[nxt][cge-c])\n",
    "        return min(dp[end])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nxt = defaultdict(list)\n",
    "        for u, v, w in paths:\n",
    "            nxt[u].append((v, w))\n",
    "            nxt[v].append((u, w))\n",
    "        d, pq = {}, [(0, start, 0)]\n",
    "        while pq:\n",
    "            w, u, c = heappop(pq)\n",
    "            if (u, c) in d:\n",
    "                continue\n",
    "            if (u, c) == (end, 0):\n",
    "                return w\n",
    "            d[(u, c)] = w\n",
    "            for v, w2 in nxt[u]:\n",
    "                if c>=w2 and (v, c-w2) not in d:\n",
    "                    heappush(pq, (w+w2, v, c-w2))\n",
    "            if c<cnt:\n",
    "                heappush(pq, (w+charge[u], u, c+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nxt = defaultdict(list)\n",
    "        for u, v, w in paths:\n",
    "            nxt[u].append((v, w))\n",
    "            nxt[v].append((u, w))\n",
    "        d, pq = {}, [(0, start, 0)]\n",
    "        while pq:\n",
    "            w, u, c = heappop(pq)\n",
    "            if (u, c) in d:\n",
    "                continue\n",
    "            if (u, c) == (end, 0):\n",
    "                return w\n",
    "            d[(u, c)] = w\n",
    "            for v, w2 in nxt[u]:\n",
    "                if c>=w2 and (v, c-w2) not in d:\n",
    "                    heappush(pq, (w+w2, v, c-w2))\n",
    "            if c<cnt:\n",
    "                heappush(pq, (w+charge[u], u, c+1))\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        g = [ [] for _ in range(len(charge)) ]\n",
    "        for u, v, w in paths:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        times = {}\n",
    "        Q = [ (0, start, 0) ]\n",
    "        def dijkastra():\n",
    "            while Q:\n",
    "                t, u, c = heappop(Q)\n",
    "                if (u, c) in times:\n",
    "                    continue\n",
    "                if (u, c) == (end, 0):\n",
    "                    return t\n",
    "                times[(u, c)] = t\n",
    "                for v, w in g[u]:\n",
    "                    if c >= w and (v, c - w) not in times:\n",
    "                        heappush(Q, (t + w, v, c - w))\n",
    "                # 留在本城市 --- 电量不满就可以充电！！！精髓之处\n",
    "                if c < cnt:\n",
    "                    heappush(Q, ( t + charge[u], u, c+1 ) )\n",
    "            \n",
    "        return dijkastra()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from heapq import heappop, heappush\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = float('inf')\n",
    "\n",
    "    def electricCarPlan(self, paths, cnt, start, end, charge):\n",
    "        nxt = defaultdict(list)\n",
    "        for u, v, w in paths:\n",
    "            nxt[u].append((v, w))\n",
    "            nxt[v].append((u, w))\n",
    "        d, pq = {}, [(0, start, 0)]\n",
    "        while pq:\n",
    "            w, u, c = heappop(pq)\n",
    "            if (u, c) in d:\n",
    "                continue\n",
    "            if (u, c) == (end, 0):\n",
    "                return w\n",
    "            d[(u, c)] = w\n",
    "            for v, w2 in nxt[u]:\n",
    "                if c>=w2 and (v, c-w2) not in d:\n",
    "                    heappush(pq, (w+w2, v, c-w2))\n",
    "            if c<cnt:\n",
    "                heappush(pq, (w+charge[u], u, c+1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nxt = defaultdict(list)\n",
    "        for u, v, w in paths:\n",
    "            nxt[u].append((v, w))\n",
    "            nxt[v].append((u, w))\n",
    "        d, pq = {}, [(0, start, 0)]\n",
    "        while pq:\n",
    "            w, u, c = heappop(pq)\n",
    "            if (u, c) in d:\n",
    "                continue\n",
    "            if (u, c) == (end, 0):\n",
    "                return w\n",
    "            d[(u, c)] = w\n",
    "            for v, w2 in nxt[u]:\n",
    "                if c>=w2 and (v, c-w2) not in d:\n",
    "                    heappush(pq, (w+w2, v, c-w2))\n",
    "            if c<cnt:\n",
    "                heappush(pq, (w+charge[u], u, c+1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        nxt = defaultdict(list)\n",
    "        for u,v,w in paths:\n",
    "            nxt[u].append((v, w))\n",
    "            nxt[v].append((u, w))\n",
    "        d, pq = {}, [(0, start, 0)]\n",
    "        while pq:\n",
    "            #使用优先队列\n",
    "            w,u,c=heappop(pq)\n",
    "            # 跳过已经访问过的状态\n",
    "            if (u,c) in d:\n",
    "                continue\n",
    "            # 到达终点直接返回结果\n",
    "            if (u,c)==(end,0):\n",
    "                return w\n",
    "            d[(u,c)]=w\n",
    "            # 转移到其相邻的城市\n",
    "            for v,w2 in nxt[u]:\n",
    "                #不需要在当前城市额外充电\n",
    "                if c>=w2 and (v,c-w2) not in d:\n",
    "                    heappush(pq,(w+w2,v,c-w2))\n",
    "            if c<cnt:\n",
    "                heappush(pq,(w+charge[u],u,c+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        #copy\n",
    "        nxt = defaultdict(list)\n",
    "        for u,v,w in paths:\n",
    "            nxt[u].append((v,w))\n",
    "            nxt[v].append((u,w))\n",
    "\n",
    "        d,pq = {},[(0,start,0)]\n",
    "        while pq:\n",
    "            w,u,c = heappop(pq)\n",
    "            if (u,c)  in d:\n",
    "                continue\n",
    "            if (u,c) == (end,0):\n",
    "                return w\n",
    "            d[(u,c)] = w\n",
    "            for v,w2 in nxt[u]:\n",
    "                if c >= w2 and (v,c-w2) not in d:\n",
    "                    heappush(pq,(w+w2,v,c-w2))\n",
    "            if c <cnt:\n",
    "                heappush(pq,(w+charge[u],u,c+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        g = [ [] for _ in range(len(charge)) ]\n",
    "        for u, v, w in paths:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        D = {}\n",
    "        Q = [ (0, start, 0) ]\n",
    "        def dijkastra():\n",
    "            while Q:\n",
    "                t, u, e = heappop(Q)\n",
    "                if (u, e) == (end, 0):\n",
    "                    return t\n",
    "                if (u, e) in D:\n",
    "                    continue\n",
    "                D[(u,e)] = t\n",
    "                for v, w in g[u]:\n",
    "                    if e >= w and (v,e-w) not in D:\n",
    "                        heappush(Q, (t+w, v, e-w))\n",
    "                if e < cnt:\n",
    "                    heappush(Q, ( t+charge[u], u, e+1 ))\n",
    "        return dijkastra()\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        #dijkstra\n",
    "        nxt = defaultdict(list)\n",
    "        for u, v, w in paths:\n",
    "            nxt[u].append((v, w))\n",
    "            nxt[v].append((u, w))\n",
    "        d, pq = {}, [(0, start, 0)]\n",
    "        while pq:\n",
    "            w, u, c = heappop(pq)\n",
    "            if(u, c) in d:\n",
    "                continue;\n",
    "            if (u, c) == (end, 0):\n",
    "                return w\n",
    "            d[(u,c)] = w\n",
    "            for v, w2 in nxt[u]:\n",
    "                if c >= w2 and (v, c - w2) not in d:\n",
    "                    heappush(pq, (w+w2, v, c - w2))\n",
    "                if c < cnt:\n",
    "                    heappush(pq, (w+charge[u], u, c+1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        dic = collections.defaultdict(dict)\n",
    "        for i, j, x in paths:\n",
    "            if j not in dic[i] or dic[i][j] > x:\n",
    "                dic[i][j] = x\n",
    "            if i not in dic[j] or dic[j][i] > x:\n",
    "                dic[j][i] = x\n",
    "        min_heap = []\n",
    "        # charge, energy, index\n",
    "        visited = {}\n",
    "        heapq.heappush(min_heap, (0, 0, start))\n",
    "        while min_heap:\n",
    "            part_charge, part_energy, index = heapq.heappop(min_heap)\n",
    "            if index == end:\n",
    "                return part_charge\n",
    "            if (index, part_energy) in visited:\n",
    "                continue\n",
    "            visited[(index, part_energy)] = 1\n",
    "            for next_index, cost in dic[index].items():\n",
    "                if part_energy > cost:\n",
    "                    heapq.heappush(min_heap, (part_charge + cost ,part_energy - cost, next_index))\n",
    "                else:\n",
    "                    heapq.heappush(min_heap ,(part_charge + cost + (cost - part_energy) * charge[index], 0, next_index))\n",
    "            if part_energy + 1 <= cnt:\n",
    "                heapq.heappush(min_heap, (part_charge + charge[index], part_energy + 1, index))\n",
    "        return -1\n",
    "\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        dic = collections.defaultdict(dict)\n",
    "        for u, v, w in paths:\n",
    "            if v not in dic[u] or dic[u][v] > w:\n",
    "                dic[u][v] = w\n",
    "            if u not in dic[v] or dic[v][u] > w:\n",
    "                dic[v][u] = w\n",
    "        visited = {}\n",
    "        min_heap = []\n",
    "        heapq.heappush(min_heap, (0, 0, start))\n",
    "        while min_heap:\n",
    "            part_charge, part_energy, index = heapq.heappop(min_heap)\n",
    "            if index == end:\n",
    "                return part_charge\n",
    "            if (part_energy, index) in visited:\n",
    "                continue\n",
    "            visited[(part_energy, index)] = 1\n",
    "            for next_index, cost in dic[index].items():\n",
    "                if part_energy >= cost:\n",
    "                    heapq.heappush(min_heap, (part_charge + cost, part_energy - cost, next_index))\n",
    "                else:\n",
    "                    heapq.heappush(min_heap, (part_charge + cost + (cost - part_energy) * charge[index], 0, next_index))\n",
    "            if part_energy + 1 <= cnt:\n",
    "                heapq.heappush(min_heap, (part_charge + charge[index], part_energy + 1, index))\n",
    "        \n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths, cnt: int, start: int, end: int, charge) -> int:\n",
    "        # 建图只取重复边中耗时最小的\n",
    "        dis = defaultdict(dict)\n",
    "        for i, j, x in paths:\n",
    "            if j not in dis[i] or x < dis[i][j]:\n",
    "                dis[i][j] = x\n",
    "            if i not in dis[j] or x < dis[j][i]:\n",
    "                dis[j][i] = x\n",
    "        \n",
    "        # 使用小顶堆进行优先状态转移\n",
    "        stack = [[0, (start, 0)]]\n",
    "        visit = {}\n",
    "        while stack:\n",
    "            cost = heapq.heappop(stack)\n",
    "            city, energy = cost[1]\n",
    "            # 到达终点直接返回结果\n",
    "            if city == end:\n",
    "                return cost[0]\n",
    "            # 跳过已经访问过的状态\n",
    "            if (city, energy) in visit:\n",
    "                continue\n",
    "            visit[(city, energy)] = 1\n",
    "            # 转移到其相邻的城市\n",
    "            for nex, distance in dis[city].items():\n",
    "                if distance < energy:\n",
    "                    cost_nex = distance + cost[0]\n",
    "                    heapq.heappush(stack, [cost_nex, (nex, energy - distance)])\n",
    "                else:\n",
    "                    cost_nex = distance + cost[0] + (distance - energy) * charge[city]\n",
    "                    heapq.heappush(stack, [cost_nex, (nex, 0)])\n",
    "            # 原地充电\n",
    "            if energy + 1 <= cnt:\n",
    "                heapq.heappush(stack, [cost[0] + charge[city], (city, energy + 1)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths, cnt: int, start: int, end: int, charge) -> int:\n",
    "        # 建图只取重复边中耗时最小的\n",
    "        dis = defaultdict(dict)\n",
    "        for i, j, x in paths:\n",
    "            if j not in dis[i] or x < dis[i][j]:\n",
    "                dis[i][j] = x\n",
    "            if i not in dis[j] or x < dis[j][i]:\n",
    "                dis[j][i] = x\n",
    "        \n",
    "        # 使用小顶堆进行优先状态转移\n",
    "        stack = [[0, (start, 0)]]\n",
    "        visit = {}\n",
    "        while stack:\n",
    "            cost = heapq.heappop(stack)\n",
    "            city, energy = cost[1]\n",
    "            # 到达终点直接返回结果\n",
    "            if city == end:\n",
    "                return cost[0]\n",
    "            # 跳过已经访问过的状态\n",
    "            if (city, energy) in visit:\n",
    "                continue\n",
    "            visit[(city, energy)] = 1\n",
    "            # 转移到其相邻的城市\n",
    "            for nex, distance in dis[city].items():\n",
    "                if distance < energy:\n",
    "                    cost_nex = distance + cost[0]\n",
    "                    heapq.heappush(stack, [cost_nex, (nex, energy - distance)])\n",
    "                else:\n",
    "                    cost_nex = distance + cost[0] + (distance - energy) * charge[city]\n",
    "                    heapq.heappush(stack, [cost_nex, (nex, 0)])\n",
    "            # 原地充电\n",
    "            if energy + 1 <= cnt:\n",
    "                heapq.heappush(stack, [cost[0] + charge[city], (city, energy + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        edges = [[] for _ in range(n)]\n",
    "        new_edges = [[[] for _ in range(cnt+1)]for i in range(n)]\n",
    "        for path in paths:\n",
    "            edges[path[0]].append((path[1],path[2]))\n",
    "            edges[path[1]].append((path[0],path[2]))\n",
    "            for i in range(path[2],cnt+1):\n",
    "                new_edges[path[0]][i].append((path[1],i-path[2],path[2]))\n",
    "                new_edges[path[1]][i].append((path[0],i-path[2],path[2]))\n",
    "        for i in range(n):\n",
    "            for j in range(cnt):\n",
    "                new_edges[i][j].append((i,j+1,charge[i]))\n",
    "        distance = [[10**9]*(cnt+1) for _ in range(n)]\n",
    "        distance[start][0] = 0\n",
    "        q = [(0,start,0)]\n",
    "        while q:\n",
    "            min_val,index_i,index_j = heapq.heappop(q)\n",
    "            if index_i==end and index_j==0:\n",
    "               return min_val\n",
    "            for edge in new_edges[index_i][index_j]:\n",
    "                if distance[edge[0]][edge[1]]>distance[index_i][index_j]+edge[2]:\n",
    "                    distance[edge[0]][edge[1]]=distance[index_i][index_j]+edge[2]\n",
    "                    heapq.heappush(q,(distance[edge[0]][edge[1]],edge[0],edge[1]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "        def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) ->int:\n",
    "            num=len(charge)\n",
    "            isConnected=[[0 for _ in range(num)] for _ in range(num)]\n",
    "            f=[[math.inf for _ in range(num)] for _ in range(num)]\n",
    "            for x,y,z in paths:\n",
    "                isConnected[x][y]=1\n",
    "                isConnected[y][x]=1\n",
    "                f[x][y]=min(f[x][y],z)\n",
    "                f[y][x]=min(f[y][x],z)\n",
    "                \n",
    "            num=len(charge)\n",
    "            graph=dict([((i,j),[]) for i in range(num) for j in range(cnt+1)])\n",
    "            for i in range(num):\n",
    "                for j in range(cnt+1):\n",
    "                    c0=[(charge[i],(i,j+1))] if j+1<=cnt else []\n",
    "                    c1=[(f[i][next_i],(next_i,j-f[i][next_i])) for next_i in range(num) if isConnected[i][next_i] and j-f[i][next_i]>=0]\n",
    "                    graph[(i,j)]=c0+c1\n",
    "\n",
    "            visited=dict([(node,False) for node in graph.keys()])\n",
    "            w=dict([(node,math.inf) for node in graph.keys()])\n",
    "            queue=[]\n",
    "            queue.append( [0,(start,0)] )\n",
    "            heapq.heapify(queue)\n",
    "\n",
    "            while queue:\n",
    "                base=heapq.heappop(queue)\n",
    "                if not visited[base[1]]:\n",
    "                    w[base[1]]=base[0]\n",
    "                    visited[base[1]]=True\n",
    "                    for nodes in graph[base[1]]:\n",
    "                        heapq.heappush (queue, [base[0]+nodes[0], nodes[1]])\n",
    "                        \n",
    "            return min([w[val] for val in graph.keys() if val[0]==end])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def dijkstra(self,graph,start):\n",
    "            queue=[[2147483647,node] for node in graph.keys()]\n",
    "            visited=set()\n",
    "            distances=dict()\n",
    "            queue.append([0,start])\n",
    "            heapq.heapify(queue)\n",
    "\n",
    "            while queue!=[]:\n",
    "                # 每次从unvisited中找到最小值所在的节点，将其从unvisited中移除\n",
    "                min_node=heapq.heappop(queue)\n",
    "                if min_node[1] not in visited:\n",
    "                    distances[min_node[1]]=min_node[0]\n",
    "                    visited.add(min_node[1])\n",
    "                    # 更新min_node所有邻接节点的距离\n",
    "                    for neighbor in graph[min_node[1]]:\n",
    "                        heapq.heappush(queue,[min_node[0]+neighbor[1],neighbor[0]])\n",
    "                    \n",
    "            return distances\n",
    "\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        # dijkstra算法，用(城市,电量)作为一个节点\n",
    "        n=len(charge)\n",
    "        neighbors={node:[] for node in [(i,j) for i in range(n) for j in range(cnt+1)]}\n",
    "        for i in range(n):\n",
    "            for j in range(cnt):\n",
    "                neighbors[(i,j)].append(((i,j+1),charge[i]))\n",
    "        for path in paths:\n",
    "            for j in range(path[2],cnt+1):\n",
    "                neighbors[(path[0],j)].append(((path[1],j-path[2]),path[2]))\n",
    "                neighbors[(path[1],j)].append(((path[0],j-path[2]),path[2]))\n",
    "        \n",
    "        \n",
    "\n",
    "        distances=self.dijkstra(neighbors, (start,0))\n",
    "        return distances[(end,0)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "        def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) ->int:\n",
    "            #城市数量\n",
    "            n=len(charge)\n",
    "            isConnected=[[False for _ in range(n)] for _ in range(n)]\n",
    "            fuel=[[math.inf for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "            for val in paths:\n",
    "                i,j,c=val\n",
    "                isConnected[i][j]=True\n",
    "                isConnected[j][i]=True\n",
    "                fuel[i][j]=min(fuel[i][j],c)\n",
    "                fuel[j][i]=min(fuel[j][i],c)\n",
    "        \n",
    "            #transition between nodes (城市，电量)\n",
    "            graph=dict()\n",
    "            for i in range(n): #城市\n",
    "                for j in range(cnt+1): #电量\n",
    "                    add_fuel=[[charge[i],(i,j+1)]] if j+1<=cnt else []\n",
    "                    add_travel=[[fuel[i][i_next], (i_next,j-fuel[i][i_next])] for i_next in range(n) if isConnected[i][i_next] and j-fuel[i][i_next]>=0]\n",
    "                    graph[(i,j)]=add_fuel+add_travel\n",
    "\n",
    "            visited=dict([(node, False) for node in graph.keys()])\n",
    "            w= dict([(node, math.inf) for node in graph.keys()])\n",
    "            queue=[[math.inf, node] for node in graph.keys()] #[时间，（城市，电量）]\n",
    "            w[(start,0)]=0\n",
    "            queue.append([0,(start,0)])\n",
    "            #初始化后heapify\n",
    "            heapq.heapify(queue)\n",
    "\n",
    "            while queue:\n",
    "                min_node= heapq.heappop(queue)\n",
    "                if not visited[min_node[1]]:\n",
    "                    w[min_node[1]]=min_node[0]\n",
    "                    visited[min_node[1]]=True\n",
    "                    for neighbor in graph[min_node[1]]:\n",
    "                        heapq.heappush(queue, [min_node[0]+neighbor[0], neighbor[1]])\n",
    "                        \n",
    "            return min([w[(end,i)] for i in range(cnt+1)])\n",
    "\n",
    "            \n",
    "                        \n",
    "            #return min([w[(end,i)] for i in range(cnt+1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        # dijkstra算法，用(城市,电量)作为一个节点\n",
    "        n=len(charge)\n",
    "        neighbors={node:[] for node in [(i,j) for i in range(n) for j in range(cnt+1)]}\n",
    "        for i in range(n):\n",
    "            for j in range(cnt):\n",
    "                neighbors[(i,j)].append(((i,j+1),charge[i]))\n",
    "        for path in paths:\n",
    "            for j in range(path[2],cnt+1):\n",
    "                neighbors[(path[0],j)].append(((path[1],j-path[2]),path[2]))\n",
    "                neighbors[(path[1],j)].append(((path[0],j-path[2]),path[2]))\n",
    "        \n",
    "        def dijkstra(graph,start):\n",
    "            queue=[[2147483647,node] for node in graph.keys()]\n",
    "            visited=set()\n",
    "            distances=dict()\n",
    "            queue.append([0,start])\n",
    "            heapq.heapify(queue)\n",
    "\n",
    "            while queue!=[]:\n",
    "                # 每次从unvisited中找到最小值所在的节点，将其从unvisited中移除\n",
    "                min_node=heapq.heappop(queue)\n",
    "                if min_node[1] not in visited:\n",
    "                    distances[min_node[1]]=min_node[0]\n",
    "                    visited.add(min_node[1])\n",
    "                    # 更新min_node所有邻接节点的距离\n",
    "                    for neighbor in graph[min_node[1]]:\n",
    "                        heapq.heappush(queue,[min_node[0]+neighbor[1],neighbor[0]])\n",
    "                    \n",
    "            return distances\n",
    "\n",
    "        distances=dijkstra(neighbors, (start,0))\n",
    "        return distances[(end,0)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        dist = [[inf]*(cnt+1) for _ in range(n)]\n",
    "        dist[start][0] = 0\n",
    "        q = [(0,start,0)]\n",
    "        g = [[]*(n) for _ in range(n) ]\n",
    "        for x,y,z in paths:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        \n",
    "        while q:\n",
    "            d,v,t = heappop(q)\n",
    "            if d > dist[v][t]:\n",
    "                continue\n",
    "            if t < cnt:\n",
    "                heappush(q,(charge[v]+d,v,t+1))\n",
    "                dist[v][t+1] = charge[v]+d\n",
    "            if v == end:\n",
    "                return d\n",
    "            for y,z in g[v]:\n",
    "                if t >= z and d+z < dist[y][t-z]:\n",
    "                    dist[y][t-z] = d+z\n",
    "                    heappush(q,(d+z,y,t-z))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq \n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = float('inf')\n",
    "\n",
    "    def electricCarPlan(self, paths, cnt, start, end, charge):\n",
    "        \"\"\"\n",
    "        求解从出发点到达终点的最短用时\n",
    "        Args:\n",
    "            paths (list[int]):\n",
    "            cnt (int):\n",
    "            start (int):\n",
    "            end (int):\n",
    "            charge (list[int]):\n",
    "        returns (int):\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if paths == None or len(paths) == 0 or cnt == None or cnt == 0 or start == None or end == None or charge == None:\n",
    "            return -1\n",
    "        \n",
    "        #创建图\n",
    "        graph = defaultdict(list)\n",
    "        for path in paths:\n",
    "            node1, node2, edge_len = path \n",
    "            graph[node1].append([node2, edge_len])\n",
    "            graph[node2].append([node1, edge_len])\n",
    "        \n",
    "        #使用小根堆保存从出发点到达各个节点所花费的最短的路径(时间), \n",
    "        #(wasted_time, node, left_charge)分别表示(到达该节点所花费的时间, 节点编号, 剩余的油量)\n",
    "        heap = [[0, start, 0]]\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        least_time_dict = defaultdict(int)  #key: (node, left_charge), value: wasted_time\n",
    "        #使用dijkstra算法求解到达终点的最短路径\n",
    "        #遍历小根堆\n",
    "        while heap:\n",
    "            #取出堆顶元素\n",
    "            w, cur_node, left_charge = heappop(heap)\n",
    "            \n",
    "            #case1.若该节点已经被访问过(已经求解得到了最短路径), 直接跳过 \n",
    "            if least_time_dict.__contains__(cur_node):\n",
    "                continue\n",
    "            \n",
    "            # case2.若该元素即为终点节点且剩余的电量为0, 直接返回\n",
    "            if (cur_node, left_charge) == (end, 0):\n",
    "                return w \n",
    "            \n",
    "            least_time_dict[(cur_node, left_charge)] = w\n",
    "            \n",
    "            #case3.探索该节点的邻接节点, 更新小根堆\n",
    "            for neighbor_node, edge_len in graph[cur_node]:\n",
    "                #还未确认过最短路径\n",
    "                if left_charge >= edge_len and (neighbor_node, left_charge - edge_len) not in least_time_dict:\n",
    "                    heappush(heap, [w + edge_len, neighbor_node, left_charge - edge_len])  #(wasted_time, node, left_charge)\n",
    "\n",
    "            #若当前节点的剩余油量小于cnt, 加油\n",
    "            if left_charge < cnt:\n",
    "                heappush(heap, [w + charge[cur_node], cur_node, left_charge + 1])\n",
    "                    \n",
    "        #return\n",
    "        return -1 \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        graph = paths\n",
    "        node_cnt = len(charge) * (cnt+1)\n",
    "        nb_dic = {}\n",
    "        for edge in graph:\n",
    "            node_from, node_to, cost = edge\n",
    "            if node_from not in nb_dic:\n",
    "                nb_dic[node_from] = []\n",
    "            nb_dic[node_from].append((node_to, cost))\n",
    "            if node_to not in nb_dic:\n",
    "                nb_dic[node_to] = []\n",
    "            nb_dic[node_to].append((node_from, cost))\n",
    "\n",
    "        q = [(0, start,0)]\n",
    "        dis = [float('inf')] * node_cnt\n",
    "        dis[start*(cnt+1)] = 0\n",
    "        vis = set()\n",
    "        while len(q) > 0:\n",
    "            c = heapq.heappop(q)\n",
    "            if c[0] != dis[c[1]*(cnt+1)+c[2]]:\n",
    "                continue\n",
    "            if c[1]==end:\n",
    "                return dis[c[1]*(cnt+1)]\n",
    "            vis.add(c[1]*(cnt+1)+c[2])\n",
    "\n",
    "            for cur_charge in range(c[2]+1,cnt+1):\n",
    "                idx1 = c[1]*(cnt+1)\n",
    "                idx3 = idx1 + cur_charge\n",
    "                if idx3 not in vis:\n",
    "                    idx2 = idx1 + c[2]\n",
    "                    cost = dis[idx2]+(cur_charge-c[2])*charge[c[1]]\n",
    "                    if cost<dis[idx3]:\n",
    "                        dis[idx3] = cost\n",
    "                        heapq.heappush(q,(cost,c[1],cur_charge))\n",
    "            for nb_node, cost in nb_dic[c[1]]:\n",
    "                if c[2]>=cost:\n",
    "                    idx0 = c[1]*(cnt+1)\n",
    "                    idx1 = nb_node*(cnt+1)\n",
    "                    idx2 = c[2]-cost\n",
    "                    idx3 = idx1+idx2\n",
    "                    if idx3 not in vis:\n",
    "                        cost = dis[idx0+c[2]] + cost\n",
    "                        if cost < dis[idx3]:\n",
    "                            dis[idx3] = cost\n",
    "                            heapq.heappush(q, (cost, nb_node, idx2))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, p: List[List[int]], c: int, st: int, end: int, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        s = [(0, st, 0)]\n",
    "        g = defaultdict(list)\n",
    "        for x, y, val in p:\n",
    "            g[x].append([y, val])\n",
    "            g[y].append([x, val])\n",
    "        v = set()\n",
    "        heapq.heapify(s)\n",
    "        while s:\n",
    "            cost, j, cha = heapq.heappop(s)\n",
    "            if j==end:\n",
    "                return cost \n",
    "            if (j, cha) in v:\n",
    "                continue \n",
    "            v.add((j, cha))\n",
    "            for up in range(cha+1, c+1):\n",
    "                heapq.heappush(s, (cost + a[j]*(up-cha), j, up))\n",
    "            for y, val in g[j]:\n",
    "                if cha>=val:\n",
    "                    heapq.heappush(s, (cost + val, y, cha - val)) \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n=len(charge)\n",
    "        grap=[[]for i in range(n)]\n",
    "        for x,y,cost in paths:\n",
    "            grap[x].append((y,cost))\n",
    "            grap[y].append((x,cost))\n",
    "        que=[(0,start,0)]\n",
    "        visited=set()\n",
    "        while(que):\n",
    "            d,p,c=heapq.heappop(que) # 花费，位置，电量\n",
    "            if p==end:\n",
    "                return d\n",
    "            #选择1 充电i度电 i+c<=cnt\n",
    "            if ((p,c) in visited):\n",
    "                continue\n",
    "            visited.add((p,c))\n",
    "        \n",
    "            for i in range(1,cnt-c+1):\n",
    "                if (p,c+i) not in visited:\n",
    "                    \n",
    "                    heapq.heappush(que,(d+i*charge[p],p,c+i))\n",
    "   \n",
    "            #选择去下一个地方\n",
    "            for nxtp,dist in grap[p]: # 第二种选择，走到相邻节点，注意电量够才能走，要判断一下\n",
    "                if dist<=c and (nxtp,c-dist) not in visited:\n",
    "                    heapq.heappush(que,(d+dist,nxtp,c-dist))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "\n",
    "        table = [set() for _ in range(len(charge))]\n",
    "\n",
    "        for x,y,d in paths: #有重边也没关系，反正重边里距离长的肯定不优\n",
    "            table[x].add((y,d))\n",
    "            table[y].add((x,d))\n",
    "        \n",
    "        que = [(0,start,0)] #初始节点为位置start，电量为0，初始节点对应的时间为0\n",
    "        visited = set()\n",
    "        while que:\n",
    "            d,p,left=heapq.heappop(que)\n",
    "            if p==end:\n",
    "                return d\n",
    "            if (p,left) in visited: #已经处理过的节点不用重复处理\n",
    "                continue\n",
    "            visited.add((p,left))\n",
    "            for nxtl in range(left+1,cnt+1): # 第一种选择，充电，注意不能充爆\n",
    "                if (p,nxtl) not in visited:\n",
    "                    heapq.heappush(que,(d+charge[p]*(nxtl-left),p,nxtl))\n",
    "            for nxtp,dist in table[p]: # 第二种选择，走到相邻节点，注意电量够才能走，要判断一下\n",
    "                if dist<=left and (nxtp,left-dist) not in visited:\n",
    "                    heapq.heappush(que,(d+dist,nxtp,left-dist))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        min_cost = {(start, 0): 0}\n",
    "        queue = [(0, start, 0)]\n",
    "        d = defaultdict(list)\n",
    "        for x, y, t in paths:\n",
    "            d[x].append([y, t])\n",
    "            d[y].append([x, t])\n",
    "        while queue:\n",
    "            cur_cost, cur_index, cur_charge = heappop(queue)\n",
    "            if cur_index == end:\n",
    "                return cur_cost\n",
    "            if cur_cost > min_cost.get((cur_index, cur_charge), 1000000):\n",
    "                continue\n",
    "            for nxt_index, need_charge in d[cur_index]:\n",
    "                for add in range(max(need_charge - cur_charge, 0), cnt - cur_charge + 1):\n",
    "                    nxt_cost = cur_cost + add * charge[cur_index] + need_charge\n",
    "                    nxt_charge = cur_charge + add - need_charge\n",
    "                    if (nxt_index, nxt_charge) not in min_cost or min_cost[(nxt_index, nxt_charge)] > nxt_cost:\n",
    "                        min_cost[(nxt_index, nxt_charge)] = nxt_cost\n",
    "                        heappush(queue, (nxt_cost, nxt_index, nxt_charge))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        table = [set() for _ in range(len(charge))]\n",
    "\n",
    "        for x,y,d in paths: #有重边也没关系，反正重边里距离长的肯定不优\n",
    "            table[x].add((y,d))\n",
    "            table[y].add((x,d))\n",
    "        \n",
    "        que = [[0,start,0]] #初始节点为位置start，电量为0，初始节点对应的时间为0\n",
    "        visited = set()\n",
    "        while que:\n",
    "            d,p,left=heapq.heappop(que)\n",
    "            if p==end:\n",
    "                return d\n",
    "            if (p,left) in visited: #已经处理过的节点不用重复处理\n",
    "                continue\n",
    "            visited.add((p,left))\n",
    "            for nxtl in range(left+1,cnt+1): # 第一种选择，充电，注意不能充爆\n",
    "                if (p,nxtl) not in visited:\n",
    "                    heapq.heappush(que,[d+charge[p]*(nxtl-left),p,nxtl])\n",
    "            for nxtp,dist in table[p]: # 第二种选择，走到相邻节点，注意电量够才能走，要判断一下\n",
    "                if dist<=left and (nxtp,left-dist) not in visited:\n",
    "                    heapq.heappush(que,[d+dist,nxtp,left-dist])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "\n",
    "        table = [set() for _ in range(len(charge))]\n",
    "\n",
    "        for x,y,d in paths: #有重边也没关系，反正重边里距离长的肯定不优\n",
    "            table[x].add((y,d))\n",
    "            table[y].add((x,d))\n",
    "        \n",
    "        que = [[0,start,0]] #初始节点为位置start，电量为0，初始节点对应的时间为0\n",
    "        visited = set()\n",
    "        while que:\n",
    "            d,p,left=heapq.heappop(que)\n",
    "            if p==end:\n",
    "                return d\n",
    "            if (p,left) in visited: #已经处理过的节点不用重复处理\n",
    "                continue\n",
    "            visited.add((p,left))\n",
    "            for nxtl in range(left+1,cnt+1): # 第一种选择，充电，注意不能充爆\n",
    "                if (p,nxtl) not in visited:\n",
    "                    heapq.heappush(que,[d+charge[p]*(nxtl-left),p,nxtl])\n",
    "            for nxtp,dist in table[p]: # 第二种选择，走到相邻节点，注意电量够才能走，要判断一下\n",
    "                if dist<=left and (nxtp,left-dist) not in visited:\n",
    "                    heapq.heappush(que,[d+dist,nxtp,left-dist])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, v, w):\n",
    "        self.v = v\n",
    "        self.w = w\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        tables = [[] for i in range(len(charge))]\n",
    "        for path in paths:\n",
    "            u, v, w = path\n",
    "            tables[u].append(Node(v, w))\n",
    "            tables[v].append(Node(u, w))\n",
    "\n",
    "        queue = [[0, start, 0]]\n",
    "\n",
    "        vis = set()\n",
    "\n",
    "        while len(queue) != 0:\n",
    "            cost, u, time = heapq.heappop(queue)\n",
    "            if u == end:\n",
    "                return cost\n",
    "            \n",
    "            if (u, time) in vis:\n",
    "                continue\n",
    "\n",
    "            vis.add((u, time))\n",
    "\n",
    "            for i in range(time + 1, cnt + 1):\n",
    "                if (u, i) not in vis:\n",
    "                    heapq.heappush(queue, [charge[u] * (i - time) + cost, u, i])\n",
    "            \n",
    "            for node in tables[u]:\n",
    "                v, w = node.v, node.w\n",
    "                if time >= w and (v, time - w) not in vis:\n",
    "                    heapq.heappush(queue, [cost + w, v, time - w])\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        grpah = {}\n",
    "        for path in paths:\n",
    "            if path[0] not in grpah:\n",
    "                grpah[path[0]] = [(path[1], path[2])]\n",
    "            else:\n",
    "                grpah[path[0]].append((path[1], path[2]))\n",
    "            \n",
    "            if path[1] not in grpah:\n",
    "                grpah[path[1]] = [(path[0], path[2])]\n",
    "            else:\n",
    "                grpah[path[1]].append((path[0], path[2]))\n",
    "\n",
    "        q = [[0, (start, 0)]]  #第一个零表示耗时，然后是结点编号，然后是电量\n",
    "        vst = set()\n",
    "        while q:\n",
    "            cost = heapq.heappop(q)\n",
    "            time = cost[0]\n",
    "            cur_node, energy = cost[1]\n",
    "\n",
    "            if cur_node == end:\n",
    "                return time\n",
    "            \n",
    "            if (cur_node, energy) in vst:\n",
    "                continue\n",
    "            vst.add((cur_node, energy))\n",
    "            for nx, nt in grpah[cur_node]:\n",
    "                if nt <= energy:\n",
    "                    heapq.heappush(q, [time + nt, (nx, energy - nt)])\n",
    "            i = 1\n",
    "            while energy + i <= cnt and (cur_node, energy + i) not in vst:\n",
    "                heapq.heappush(q, [time + charge[cur_node] * i, (cur_node, energy+i)])\n",
    "                i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:\n",
    "        n = len(charge)\n",
    "        neighbors = [[] for _ in range(n * (cnt + 1))]\n",
    "        for i in range(n):\n",
    "            for j in range(cnt + 1):\n",
    "                n1 = i * (cnt + 1) + j\n",
    "                for k in range(j):\n",
    "                    n2 = i * (cnt + 1) + k\n",
    "                    neighbors[n2].append((n1, (j - k) * charge[i]))\n",
    "\n",
    "        for i, j, k in paths:\n",
    "            for ki in range(k, cnt + 1):\n",
    "                kj = ki - k\n",
    "                n1 = i * (cnt + 1) + ki\n",
    "                n2 = j * (cnt + 1) + kj\n",
    "                neighbors[n1].append((n2, k))\n",
    "            for kj in range(k, cnt + 1):\n",
    "                ki = kj - k\n",
    "                n1 = i * (cnt + 1) + ki\n",
    "                n2 = j * (cnt + 1) + kj\n",
    "                neighbors[n2].append((n1, k))\n",
    "\n",
    "        inf = 10 ** 8\n",
    "        dist = [inf] * (n * (cnt + 1))\n",
    "        q = []\n",
    "        heapq.heappush(q, (0, start * (cnt + 1) + 0))\n",
    "        while len(q) > 0:\n",
    "            di, i = heapq.heappop(q)\n",
    "            if (dist[i] < di):\n",
    "                continue\n",
    "            else:\n",
    "                city = i // (1 + cnt)\n",
    "                if city == end:\n",
    "                    return di\n",
    "                dist[i] = di\n",
    "                for j, dj in neighbors[i]:\n",
    "                    if di + dj < dist[j]:\n",
    "                        dist[j] = di + dj\n",
    "                        heapq.heappush(q, (di + dj, j))\n",
    "        return dist\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
